class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int row_begin = 0, col_begin = n - 1;

        while (row_begin < m && col_begin >= 0)
        {
            if (matrix[row_begin][col_begin] > target)
                col_begin--;
            else if (matrix[row_begin][col_begin] < target)
                row_begin++;
            else
                return true;
        }

        return false;
    }
};